#include <cstdio>
#include <cstdlib>
#include <time.h>



#define PQ_SIZE 100



struct PriorityQueue {
  int q[PQ_SIZE]; // body of the queue
  int n;            // number of queue elements
};



void
swap(PriorityQueue* heap, int i, int j)
{
  int tmp = heap->q[i];
  heap->q[i] = heap->q[j];
  heap->q[j] = tmp;
}



void
bubble_down(PriorityQueue* heap, int pos)
{
  int left_child = 2*pos + 1;
  int min_index = pos;

  // find the dominating node among the current node and its two children
  for (int i = 0; i <= 1; ++i)
    {
      int child = left_child + i;
      if (child < heap->n)
	{
	  if (heap->q[min_index] > heap->q[child])
	    {
	      min_index = child;
	    }
	}
    }

  if (min_index != pos)
    {
      swap(heap, min_index, pos);
      bubble_down(heap, min_index);
    }
}



void
make_heap(PriorityQueue* heap, int* input, int n)
{
  heap->n = n;
  
  for (int i = 0; i < n; ++i)
    {
      heap->q[i] = input[i];
    }

  for (int i = n-1; i >= 0; --i)
    {
      bubble_down(heap, i);
    }
}




int
extract_min(PriorityQueue* heap)
{
  int min = -1;

  if (heap->n <= 0)
    {
      fprintf(stderr, "Warning: empty priority queue!");
    }
  else
    {
      min = heap->q[0];
      heap->q[0] = heap->q[heap->n - 1];
      heap->n = heap->n - 1;
      bubble_down(heap, 0);
    }

  return min;
}


// decide whether the kth smallest element of a heap is smaller than x in O(k).
int
heap_compare(PriorityQueue* heap, int index, int count, int x)
{
  if ((count <= 0) || (index > heap->n))
    {
      return count;
    }

  if (heap->q[index] < x)
    {
      int left_child = 2*index + 1;
      count = heap_compare(heap, left_child, count-1, x);
      count = heap_compare(heap, left_child+1, count, x);
    }

  return count;
}



int main(int argc, char* argv[])
{
  int n;

  if (argc == 1)
    {
      n = 10;
    }
  else
    {
      n = atoi(argv[1]);
    }

  srand ( time(NULL) );
  
  fprintf(stderr, "Original array:\n");
  int s[n];
  for (int i = 0; i < n; ++i)
    {
      s[i] = rand() % 100;
      fprintf(stderr, "%d ", s[i]);
    }
  fprintf(stderr, "\n");

  PriorityQueue heap;
  
  make_heap(&heap, s, n);

  fprintf(stderr, "Sorted array:\n");
  for (int i = 0; i < n; ++i)
    {
      s[i] = extract_min(&heap);
      fprintf(stderr, "%d ", s[i]);
    }
  fprintf(stderr, "\n");
}
